The present invention is related to the creation of structures used for computer network routing tables and, in particular, for PNNI routing tables used in ATM networks.
Asynchronous Transfer Mode (ATM) is a connection oriented system. As such, connection requests need to be routed from a requesting node though the ATM network to a destination node. The ATM Forum has defined a private network-to-network or node-to-node interface (PNNI) protocol which allows easier interconnection of ATM switches. The PNNI protocol consists of two components. The first is a signaling protocol used to relay ATM connection requests within a network between a source and a destination. The second is a routing protocol used to determine the path for routing signaling requests though the ATM network. The goal of the PNNI protocol is to advertise enough information between the nodes of a network so as to allow the nodes to route call requests within the network. Ideally, every ATM switch in a network would not only know the address of every ATM attached installation but also the current available composite (VPI/VCI) for new switched virtual circuits (SVCs) to every switch. However, as ATM networks grow to include hundreds or even thousands of switches supporting tens of thousands of users and devices, such an implementation becomes unfeasible.
Nevertheless, finding the shortest or best available path from one point to another across an ATM network does require that each node know something about what the network looks like. For example, each node must know its own whereabouts in the network and be able to locate other nodes or ATM installations so that it can establish virtual circuits offering the appropriate speed and quality of service (QoS) parameters. The solution devised by the ATM Forum is a scheme that distributes and summarizes network topologies so that nodes have detailed information about their local topology and summarized information about more distant regions of the network. The PNNI protocol manages this information through the use of an hierarchical topology, along with an addressing scheme similar to that used in telephony networks.
For each node (e.g., switch) of an ATM network, a PNNI interface associates a connection between two nodes and the connection may be a physical link or a virtual path connection (VPC). In general, every PNNI-capable node has several such interfaces and each is associated with a set of parameter (usually stored in a data structure in memory), including a traffic metrics table that stores the available traffic resource parameters on the link associated with the interface (in the forward direction). These traffic metrics tables are generally two-dimensional and associate service classes with the type of traffic metrics or attributes supported by the connection. In one sense, PNNI is a link state algorithm and QoS-based routing protocol which can collect and advertise these link state parameters (i.e., the attributes and metrics that are associated with each link and node) which become the bases for routing path selections within the network.
Using PNNI, then network nodes are provided with xe2x80x9creachability informationxe2x80x9d (i.e., based on the traffic metrics and attributes) about other nodes. This reachability information is used by a source node to construct a designated transit list (DTL) that describes a complete route to a destination node. The DTL is inserted into a signaling request which is then transmitted along the path described by the DTL. Thus, using PNNI, a single connection will be set up between the source node and the destination node.
ATM nodes configured to use the PNNI routing protocol advertise the reachability of a particular ATM address over multiple ATM physical links. The various levels of the switching hierarchy established by PNNI, map different segments of the overall ATM network in different degrees of detail. By breaking a large network of ATM switches into smaller domains called peer groups, PNNI allows individual switches to navigate paths through the entire network without requiring them to store an entire map of the network in memory. PNNI organizes nodes into peer groups and nodes within a peer group elect a leader node called a peer group leader. The peer group leader summarizes information about the peer group and presents that information to the next higher level hierarchy and also instantiates a logical group node (LGN) at the next higher level. The LGN represents its own child peer group at the lower level and becomes the peer of other LGNs at its level.
Using PNNI then, nodes in an ATM network automatically form a hierarchy of peer groups according to addresses assigned by a network manager. The nodes"" ATM addresses provide the key to the structure of this hierarchy. Each peer group has its own identifier (called a peer group ID), similar to a telephone exchange or area code. For a lower level peer group this ID is similar to an area code and exchange. For a higher peer group, it would be similar to just the area code. Finally, each node within a peer group has a unique address, similar to the way each line in a telephone exchange has a unique number.
Once the PNNI hierarchy is created, peer group leaders are allocated, and routing information is exchanged. Thereafter, the ATM nodes can begin to establish SVCs between various end-stations on the network. Using the PNNI protocol, installations on remote networks can easily establish SVCs across the hierarchy with other end stations and different peer groups.
When a signaling request is received across a user-to-network interface (UNI) by a ingress node, the node will use a shortest path algorithm, such as a Dijkstra calculation, to determine a path to connect the call to the desired destination. This calculation will create a set of DTLs, and each node will have: a full, detailed path within the source node""s own peer group; a less detailed path within the parent peer groups; and even less detail on higher level peer groups, terminating in the lowest level peer group which is an ancestor of both the source and the destination nodes. Hence, using PNNI, SVCs can be set up across a network. Once the connection is established, ATM cells are forwarded by simple table lookups, e.g., using connection tables.
As indicated above, the PNNI specification requires that QoS sensitive source routing algorithms be used in the PNNI hierarchical routing environment. QoS sensitive routing implies that the route selection algorithm must determine whether a source route can support all of the QoS requirements of a request. This requires that the routing algorithm consider both link constraints and path constraints. Link constraints such as available bandwidth (AvCR) are relatively easy to deal with because links which do not meet a caller""s requirements may simply be dropped or pruned from the topology during the shortest path calculation. However, path constraints such as cell transfer delay (CTD) and cell delay variation (CDV) are more difficult to deal with because they are not dependent on a single link only and, to date, no known routing algorithm is capable of optimizing for multiple path constraints.
Of the known routing algorithms (or shortest path algorithms), on-demand routing has gained some popularity. Indeed, one method of on-demand routing is presented as an appendix to the ATM Forum""s PNNI specification. In general, on-demand routing performs a separate route computation for each requested route. On-demand routing according to this method optimizes on a single path constraint while pruning links that do not meet the caller""s requirements.
Another routing scheme proposed in the PNNI specification uses pre-computed routes. In this case, sets of paths for each QoS (e.g., constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR)) are pre-calculated by computing the shortest path routes using a single optimization criteria for a single class of service. The routes provided are optimized without considering bandwidth (i.e., so long as a link has  greater than 0 bandwidth it is used for the shortest path computation) and the method falls back to on-demand routing every time the search of pre-computed routes fails. In general, the pre-computed routes are stored in linear routing tables. Each routing table is maintained as a shortest path tree (SPT), and each SPT is constructed based on the optimization of a single traffic metric. In other words, each SPT maintains a shortest path tree to each reachable destination node in the same PNNI routing domain based on a single criterion, i.e., a traffic metric.
The use of such conventional routing tables, however, has several undesirable effects. For example, because multiple such tables are required to accommodate all of the various traffic metrics and service classes, a considerable amount of memory is required just to store the tables. Indeed, where all service classes exist in a network, a maximum number of these tables may have to be generated and stored. Further, because known routing algorithms can only optimize on a single constraint at a time, this suggests that any SPT made up of traditional routing tables will contain only those paths optimized for the designated traffic parameter. Yet, other parameters (which were not the subject of the route optimization computation) may also be determinative of whether a given route may be used by a connection request. This further increases the demand for sufficient memory to store the necessary routing tables.
What is desired, therefore, is a method for creating routing table structures for ATM or other networks that avoids the drawbacks of prior schemes.
The present invention provides a method of dynamically creating routing table structures which may find application as routing tables for ATM or other computer networks. In general, each routing table provides a selection of pre-computed routes optimized to a specified constraint such as delay and delay variation (e.g., as measured by CTD and CDV), or administrative weight (AW). The routing tables may be implemented as shortest path trees, e.g., as may be generated by a Dijkstra process, which represent the computed routes within the network, optimized to a specified constraint for one or more specified network service categories. Thus, the routing tables allow for rapid compilation of one or more source-computed routes (e.g., DTLs in an ATM network). In some cases, the routing tables may include alternate routes between network nodes. By providing these alternate routes in a single routing table structure, the present invention may utilize less storage and processing resources as compared to routing table schemes of the past.
Thus, in one embodiment, routing tables for a computer network may be dynamically created according to traffic metrics advertised for service classes within the network (e.g., one or more additive ATM traffic metrics). Any number of tables, between a minimum of three and a maximum of ten, may be created. The traffic metrics may include administrative weight (AW), cell transfer delay (CTD) and cell delay variation (CDV) and the service classes may include constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR). Each of the routing tables preferably provides a selection of pre-computed routes within the computer network optimized to one of the traffic metrics. The routing tables may be implemented as shortest path trees, each of which represents the pre-computed routes within the computer network optimized to a specified traffic metric for one or more of the service classes. Each shortest path tree may be generated using a Dijkstra process and one or more of the routing tables may include alternate routes between nodes of the computer network. In response to a request for a connection within the network a path may be selected from an appropriate one of the routing tables.